
 #include "./ActiveEdgeTable.h"
#include <stdio.h>

// declaration so can use in drawPolygon(); is there a way around this?
//    perhaps move all of the extra functions (or those needed) into here?
void setFramebuffer(int x, int y, float R, float G, float B);
bool PointCompare(Point* p1, Point* p2);
void clip(Point* l1, Point* l2, Point c1, Point c2);
double intersection(Point p1, Point p2, Point p3, Point p4);
Point corner(Point p1, Point p2, Point p3, Point p4);




/***********************************  Point  ******************************************/


bool PointCompare(Point* p1, Point* p2)
{
        return ((p1->x == p2->x) && (p1->y == p2->y));
}






/***********************************  Edge  ******************************************/

Edge::Edge(Point _p1, Point _p2)
{
        double slope;

//      conclusion: using these stores makes no difference to drawPolygon() (which does still have problems)
        p1 = _p1;               // Maybe should just use these; think about it
        p2 = _p2;               //
        
        // Can alter this to use the ? operator, but for clarity, will use if/then for now
        if(_p1.y > _p2.y)       // _p1 is the higher y value (lower placed) point
        {
                // does the order matter?
//              p1 = _p1;       // lower placed point
//              p2 = _p2;       // higher placed point

                printf("Cap'n!:\t_p2 < _p1\n_p2:\t%d,%d\t_p1:\t%d,%d\n",_p2.x,_p2.y,_p1.x,_p1.y);
                maxY = (int)_p1.y;      // do want to keep minY, maxY as ints
                minY = (int)_p2.y;
                currentX = _p2.x;

                slope = ((double)_p1.y - (double)_p2.y)/((double)_p1.x - (double)_p2.x);        // (y2-y1)/(x2-x1)
                xIncr = 1/slope;
        
                printf("p1:\t%d,%d\tp2:\t%d,%d\ncurrentX:\t%f\txIncr:\t%f\tminY:\t%f\tmaxY:\t%f\n",
                p1.x, p1.y, p2.x, p2.y, currentX, xIncr, minY, maxY);


        }
        else if(_p2.y > _p1.y)  // _p2 is the higher y value (lower placed) point
        {
//              p1 = _p2;       // lower placed point
//              p2 = _p1;       // higher placed point

                printf("Cap'n!:\t_12 < _21\n_p1:\t%d,%d\t_p2:\t%d,%d\n",_p1.x,_p1.y,_p2.x,_p2.y);
                maxY = (int)_p2.y;      // do want to keep minY, maxY as ints
                minY = (int)_p1.y;
                currentX = _p1.x;
                
                slope = ((double)_p2.y - (double)_p1.y)/((double)_p2.x - (double)_p1.x);        // (y2-y1)/(x2-x1)
                xIncr = 1/slope;

                
                printf("p1:\t%d,%d\tp2:\t%d,%d\ncurrentX:\t%f\txIncr:\t%f\tminY:\t%f\tmaxY:\t%f\n",
                p1.x, p1.y, p2.x, p2.y, currentX, xIncr, minY, maxY);
        }
        else    // horizontal!  Choose _p1 to be max (though think it should actually just ignore this edge?)
        {
                printf("Cap'n!:\t_p1 = _p2\n");
                // do nothing
        }       
}


Edge::~Edge()  {   }    // nothing needed to implement destructor


bool
Edge::compareEdge(Edge first, Edge second)
{
        if(first.currentX < second.currentX)
                return true;
        else
                return false;
}


bool
Edge::operator<(Edge& rhs)
{
        return (this->currentX < rhs.currentX);
}


void
Edge::printEdge()
{
        printf("p1:\t%d,%d\tp2:\t%d,%d\ncurrentX:\t%f\txIncr:\t%f\tminY:\t%f\tmaxY:\t%f\n",
                p1.x, p1.y, p2.x, p2.y, currentX, xIncr, minY, maxY);
}


/***********************************  EdgeList  ******************************************/
EdgeList::EdgeList(Edge _e)
{
        this->elmaxY = _e.maxY; // store the scanline value
        this->elminY = _e.minY;
}

EdgeList::EdgeList(Edge* _e)
{
        this->elmaxY = _e->maxY;
        this->elminY = _e->minY;
}

EdgeList::EdgeList()
{
        this->elmaxY = 0;
        this->elmaxY = 0;
        printf("Cap'n!\tDefault constructor called");
}

EdgeList::~EdgeList() { 
        // delete each edge e
}       

/*
void
EdgeList::addEdge(Edge _e)
{
        edgeList.push_back(_e);
//      edgeList.sort( Edge::compareEdge );
        edgeList.sort();        // by currentX
}
*/

void
EdgeList::addEdge(Edge* _e)
{
        edgeList.push_back(_e);
        edgeList.sort();
}


void
EdgeList::printEdgeList()       // for debugging
{
        std::list<Edge*>::iterator elIter;

        // at each edge, print the two points
        for(elIter = edgeList.begin(); elIter != edgeList.end(); elIter++)
                printf("p1:\t%d,%d\tp2:\t%d,%d\n", (*elIter)->p1.x, (*elIter)->p1.y,
                        (*elIter)->p2.x, (*elIter)->p2.y);

}




// compares EdgeLists via their "y" value
bool 
EdgeList::compareEdgeList(EdgeList first, EdgeList second)
{
        if(first.elminY < second.elminY)
                return true;
        else
                return false;   
}




bool
EdgeList::operator<(EdgeList& rhs)
{
        return (this->elminY < rhs.elminY);
}



/***********************************  ActiveEdgeList  ******************************************/
/*
ActiveEdgeList::ActiveEdgeList(Edge _e)
{
        EdgeList::EdgeList(_e);
}

ActiveEdgeList::~ActiveEdgeList()
{
        EdgeList::~EdgeList
}

bool 
ActiveEdgeList::operator<(ActiveEdgeList& rhs)  // want to sort by currentX
{
        return
}
*/

/***********************************  Polygon  ******************************************/


Polygon::Polygon(int _windowWidth, int _windowHeight, Color _color) {
        windowWidth = _windowWidth;
        windowHeight = _windowHeight;   
        color = _color;

        // may be more efficient to have it be a list and add entries only when an edge is added at that entry
        //    and just keep a "line identity"
        //aeTable = new std::vector<EdgeList>;  // get a vector of list of Edges of the right size
}


Polygon::~Polygon() { 
        //delete aeTable
        //delete aeList (maybe) 
}

/*
void 
Polygon::addEdge(Edge e)        // called when the user left or right clicks
{
        printf("Regular Polygon::addEdge() called\n");
        std::list<EdgeList>::iterator iter, next;       

        for(iter = aeTable.begin(); iter != aeTable.end(); iter++)
        {
                if((*iter).elminY == e.minY)    // correct EdgeList
                {
                        (*iter).addEdge((e));   // add an edge at that point
                        return;
                }
        }

        // no correct scanline value was found 
        //    => add a new EdgeList with the correct scanline value
        EdgeList* el = new EdgeList(e);         // new EdgeList
        el->elminY = e.minY;                                            // considering proper scanline
        el->elmaxY = e.maxY;
        el->addEdge(e);                                         // add the edge to the EdgeList
        aeTable.push_back(*el);                         // stick the EdgeList in the table
//      aeTable.sort(EdgeList::compareEdgeList);                // make sure the table is in order (wrt. y)
        aeTable.sort();
}
*/



void 
Polygon::addEdge(Edge *e)
{
        std::list<EdgeList*>::iterator iter, next;
        Point* t1;
        Point* t2;
        t1 = new Point;
        t2 = new Point;
        t1->x = e->p1.x;
        t1->y = e->p1.y;

        t2->x = e->p2.x;
        t2->y = e->p2.y;

// need it now so that the vertices are ordered
        vTable.push_back(t1);
        vTable.push_back(t2);   // stick the endpoints in the vertex table
        vTable.unique(PointCompare);                    // remove any duplicates

        for(iter = aeTable.begin(); iter != aeTable.end(); iter++)
        {
                if((*iter)->elminY == e->minY)  // correct EdgeList
                {
                        (*iter)->addEdge(e);    // add an edge at that point
                        return;
                }
        }

        // no correct scanline value was found 
        //    => add a new EdgeList with the correct scanline value
        EdgeList* el = new EdgeList(e);         // new EdgeList
        el->elminY = e->minY;                                           // considering proper scanline
        el->elmaxY = e->maxY;
        el->addEdge(e);                                         // add the edge to the EdgeList
        aeTable.push_back(el);                          // stick the EdgeList in the table
//      aeTable.sort(EdgeList::compareEdgeList);                // make sure the table is in order (wrt. y)
        aeTable.sort();
}





void 
Polygon::drawPolygon()  // will be the one to call setFrameBuffer();
{
        int line = 0;   // current line being drawn
        std::list<EdgeList*>::iterator aeTableIter = aeTable.begin();
        std::list<Edge*>::iterator aeListIter;
        std::list<Edge*>::iterator EdgeListIter;
        

        while( line < windowHeight )
        {
//              printf("beginning:\n");

                // 1. Add edges to Active Edge List from Active Edge Table based on their minimum Y value
                for(aeTableIter = aeTable.begin(); aeTableIter != aeTable.end(); aeTableIter++)
                {
                        if((*aeTableIter)->elminY == line)      // there is an entry that starts at this scanline
                        {
//                              printf("1: checking table\n");
                                for(EdgeListIter = (*aeTableIter)->edgeList.begin();            // take that edge list that is valid
                                        EdgeListIter != (*aeTableIter)->edgeList.end(); EdgeListIter++) // go through it
                                {
//                                      printf("1: found edge\n");
                                        aeList.addEdge((*EdgeListIter));
//                                      printf("1: added edge\n");
//                                      aeList.push_back(*EdgeListIter);        // and add the entries into the Active Edge List
                                }
//                              printf("1: incrementing...");
//                              printf("1: incremented!\n");
                        }
                }


//              printf("1 done, ");


                // 2. Remove edges that end at that line
//              for(aeListIter = aeList.edgeList.begin(); aeListIter != aeList.edgeList.end(); aeListIter++)    
                aeListIter = aeList.edgeList.begin();
                while(aeListIter != aeList.edgeList.end())
                {               // traverse the active edge list
                        // if an edge ends at this scanline
                        if((*aeListIter)->maxY == line) 
                        {       // erase the edge
                                // erase() returns an iterator to the one after the one that was erased
                                if(aeListIter == aeList.edgeList.begin())
                                {       // was at the beginning
                                        aeListIter = aeList.edgeList.erase(aeListIter); 
                                        aeListIter = aeList.edgeList.begin();   // probably unneeded
                                        continue;
                                }
                                else
                                {
                                        aeListIter = aeList.edgeList.erase(aeListIter); // don't move the iterator
                                        continue;
                                }
//                              printf("removed ");
                        }
                        aeListIter++;
                }



                // If there is nothing in the list, there is nothing to draw and no
                //    reason to go on
                if(aeList.edgeList.empty())     // returns 1 if is empty
                {
                        line++;                                 // go to the next line and try again
//                      printf("continuing\n");
                        continue;                               
                }



//              printf("2 done\n");

                
                // 3. Fill Pixels
                bool inside = false;    // toggle pixels on and off as edges are encountered; default off
                aeList.edgeList.sort(); // sorts by currentX

                aeListIter = aeList.edgeList.begin();
                for(int i = 0; i < windowWidth; i++)    // each x coordinate at y = line
                {       
                        if(aeList.edgeList.empty())     // error checking; should never happen
                        {
                                printf("somehow it's empty.. =(\n");
                                break;
                        }
                        if(aeListIter == aeList.edgeList.end()) // if is past the last edge
                        {
                // If aeListITer == ~.~.end(), then it's PAST The last element and at (basically) a footer.
                // Thus, simply break if it's at ~.~.end()

//                              printf("break 2\n");
                                break;
                        }
                        if((*aeListIter)->currentX <= i)        // passed an edge (I think this is correct)
                        {
                                inside = !inside;                       // invert whether you're coloring or not
//                              printf("Row passed an edge:\t");
                                aeListIter++;                           // check the next edge
/*                              
                                else
                                {
                                        printf("break 3\n");
                                        break;
                                }
*/
                        }

                        if(inside)                                              // if inside a polygon
                        {
//                              printf("+");    // for debugging
                                setFramebuffer(i, line, color.r, color.g, color.b);     // color the pixel!
                        }
                        else
                        {
//                              printf(".");    // debugging
                        }
                }

//              printf("line %d\n", line);
                
//              printf("3 done, ");




                // 4. Increment x-values on edges in Active Edge List
                for(aeListIter = aeList.edgeList.begin(); aeListIter != aeList.edgeList.end(); aeListIter++)    
                {
                        (*aeListIter)->currentX += (*aeListIter)->xIncr;        // incrementing x values on all edges
                }       // don't need these braces, but w/e

//              printf("4 done\n");

                // 5. Increment line
                line++;

        }


        // empty the active edge list; should help; doesn't; the shapes are migrating.. what am I changing
        for(aeListIter = aeList.edgeList.begin(); aeListIter != aeList.edgeList.end(); 1)
        {
                printf("potentially stuck in a loop...\n");
                aeListIter = aeList.edgeList.erase(aeListIter);
        }


}




Polygon* 
Polygon::clipPolygon(Polygon* old, Point _p1, Point _p2)
{
        Polygon* clipped = new Polygon(windowWidth, windowHeight, color);       // empty polygon
        Point e1;
        Point e2;


        if((_p1.x == _p2.x) || (_p1.y == _p2.y))
        {
                printf("clipping along a line\n");
                // clipping on a line is nothing => return nothing
                return clipped;
        }

        // 1. clip each line/edge; save the endpoints;
        //      make sure that points that are out in two directions put a vertex in the corner
        //      if the next edge intersects a different side
        //           perhaps by checking if p2old.x != p1new.x || p2old.y != p1new.y

        
        std::list<Point*>::iterator pIter = vTable.begin();
//      std::list<Edge*>::iterator elIter = (*aeTable.begin())->edgeList.begin();
        Edge* tempEdge = NULL;
        Edge* tempEdge2;        // checking corners
        Edge* tempEdge3;
//      Point origin = (*(*pIter));     // first point of the vertex list

        while(pIter != vTable.end())    // while there are vertices remaining
        {
                // copy two points
                e1.x = (*pIter)->x;
                e1.y = (*pIter)->y;

                pIter++;

                if(pIter == vTable.end())
                {       // origin was already at the end; nothing to be done, break out
                        break;
                }
                e2.x = (*pIter)->x;
                e2.y = (*pIter)->y;
                
                clip(&e1, &e2, _p1, _p2);       // point is clipped

                //      make sure that points that are out in two directions put a vertex in the corner
                //      if the next edge intersects a different side
                //           perhaps by checking if p2old.x != p1new.x || p2old.y != p1new.y
                tempEdge2 = tempEdge;   // last Edge added; for corner checking
                tempEdge = new Edge(e1,e2);     // new edge

                if(tempEdge2 != NULL)   // corner checking
                {       // i.e. there was an edge before the current
                        if((tempEdge2->p2.x == tempEdge->p1.x) || (tempEdge2->p2.y == tempEdge2->p1.x))
                        {       // they are clipped along the same rectangle-edge
                                tempEdge3 = new Edge(tempEdge2->p2, tempEdge->p1);
                                clipped->addEdge(tempEdge3);
                        }
                        else
                        {       // some intervening corner
                                // find the corner
                                Point t1 = tempEdge2->p2;
                                Point t2 = tempEdge->p1;
                                // add an edge from tempEdge2->p2 to corner, and corner to e1
                                Point t3 = corner(t1, t2, _p1, _p2);    
                                tempEdge3 = new Edge(t1, t3);
                                clipped->addEdge(tempEdge3);
                                tempEdge3 = new Edge(t3, t2);
                                clipped->addEdge(tempEdge3);
                        }
                }

                // add the edge
                clipped->addEdge(tempEdge);
        }


        // strangely (and conveniently) enough, the last vertex is in the vTable 
        //    twice; this code is therefore unneeded
/*
        // reusing code to add the last edge
        // add the last edge
        e1 = e2;
        e2 = origin;
        clip(&e1, &e2, _p1, _p2);       // point is clipped

        //      make sure that points that are out in two directions put a vertex in the corner
        //      if the next edge intersects a different side
        //           perhaps by checking if p2old.x != p1new.x || p2old.y != p1new.y
        tempEdge2 = tempEdge;   // last Edge added; for corner checking
        tempEdge = new Edge(e1,e2);     // new edge

        if(tempEdge2 != NULL)   // corner checking
        {       // i.e. there was an edge before the current
                if((tempEdge2->p2.x == tempEdge->p1.x) || (tempEdge2->p2.y == tempEdge2->p1.x))
                {       // they are clipped along the same rectangle-edge
                        tempEdge3 = new Edge(tempEdge2->p2, tempEdge->p1);
                        clipped->addEdge(tempEdge3);
                }
                else
                {       // some intervening corner
                        // find the corner
                        Point t1 = tempEdge2->p2;
                        Point t2 = tempEdge->p1;
                        // add an edge from tempEdge2->p2 to corner, and corner to e1
                        Point t3 = corner(t1, t2, _p1, _p2);    
                        tempEdge3 = new Edge(t1, t3);
                        clipped->addEdge(tempEdge3);
                        tempEdge3 = new Edge(t3, t2);
                        clipped->addEdge(tempEdge3);
                }
        }

        // add the edge
        clipped->addEdge(tempEdge);
*/

        return clipped; // return the address to this clipped polygon
}




void
Polygon::printEdgeTable()
{
        std::list<EdgeList*>::iterator aeTableIter;

        for(aeTableIter = aeTable.begin(); 
                aeTableIter != aeTable.end(); aeTableIter++)
        {
                printf("Edge %d:\n", (*aeTableIter)->elminY);
                (*aeTableIter)->printEdgeList();
        }

        printf("\n");
}




        /***********************************    ******************************************/


// line endpoint 1, 2 and clipping rectangle corner 1, 2
void clip(Point* l1, Point* l2, Point c1, Point c2)     
{       // fun linear algebra stuff
//      double tb, tt, tl, tr;  // parameter value of intersection
        double t;                               // parameter value of intersection
        Point br, tr, bl, tl;   // edge1, edge2, right bottom, right top, left bottom, left top


        // will make it easier to manipulate
        if(c1.x > c2.x) // c1 is right
        {
                if(c1.y > c2.y) // c1 is bottom-right (in the inverse y coordinates we use)
                {
                        br = c1;
                        tl = c2;
                        
                        bl.x = c2.x;
                        bl.y = c1.y;

                        tr.x = c1.x;
                        tr.y = c2.y;
                }
                else    // c1 is top right
                {
                        tr = c1;
                        bl = c2;

                        br.x = c1.x;
                        br.y = c2.y;

                        tl.x = c2.x;
                        tl.y = c1.y;
                }
        }

        else if (c1.x < c2.x)   // c1 is left
        {
                if(c1.y > c2.y) // c1 is bottom left
                {
                        bl = c1;
                        tr = c2;

                        tl.x = c1.x;
                        tl.y = c2.y;

                        br.x = c2.x;
                        br.y = c1.y;
                }
                else                            // c1 is top left
                {
                        tl = c1;
                        br = c2;

                        tr.x = c2.x;
                        tr.y = c1.y;

                        bl.x = c1.x;
                        bl.y = c2.y;
                }
        }

        // left
        t = intersection((*l1), (*l2), bl, tl);
        if((t >= 0.0) && (t <= 1.0))    
        {       // it intersects left edge
                if(l1->x < l2->x)       // from outside inward
                {       // mess only with l1; l2 is inside
                        l1->x = l1->x + (l2->x - l1->x)*t;
                        l1->y = l1->y + (l2->y - l1->y)*t;
                }
                else    // from inside outward
                {       // l1 is fine; mess with l2
                        l2->x = l1->x + (l2->x - l1->x)*t;
                        l2->y = l1->y + (l2->y - l1->y)*t;
                }
        }

        // right
        t = intersection((*l1), (*l2), br, tr);
        if((t >= 0.0) && (t <= 1.0))    
        {       // it intersects right edge
                if(l1->x < l2->x)       // from inside outward
                {       // mess only with l2; l1 is inside
                        l2->x = l1->x + (l2->x - l1->x)*t;
                        l2->y = l1->y + (l2->y - l1->y)*t;
                }
                else    // from outside inward
                {       // l2 is inside; mess with l1
                        l1->x = l1->x + (l2->x - l1->x)*t;
                        l1->y = l1->y + (l2->y - l1->y)*t;
                }
        }

        // top
        t = intersection((*l1), (*l2), tl, tr);
        if((t >= 0.0) && (t <= 1.0))    
        {       // it intersects top edge
                if(l1->y < l2->y)       // from outside inward
                {       // l2 is inside; mess with l1
                        l1->x = l1->x + (l2->x - l1->x)*t;
                        l1->y = l1->y + (l2->y - l1->y)*t;
                }
                else    // from outside inward
                {       // l1 is inside; mess with l2
                        l2->x = l1->x + (l2->x - l1->x)*t;
                        l2->y = l1->y + (l2->y - l1->y)*t;
                }
        }

        // bottom
        t = intersection((*l1), (*l2), bl, br);
        if((t >= 0.0) && (t <= 1.0))    
        {       // it intersects bottom edge
                if(l1->y < l2->y)       // from inside outward
                {       // mess only with l2; l1 is inside
                        l2->x = l1->x + (l2->x - l1->x)*t;
                        l2->y = l1->y + (l2->y - l1->y)*t;
                }
                else    // from outside inward
                {       // l2 is inside; mess with l1
                        l1->x = l1->x + (l2->x - l1->x)*t;
                        l1->y = l1->y + (l2->y - l1->y)*t;
                }
        }

        // done
}

double intersection(Point p1, Point p2, Point p3, Point p4)
{       // derived from intersecting parameterized general line equations
        double x0, x1, x2, x3, y0, y1, y2, y3;  // so can easily match derived equation
        double temp1, temp2;

        x0 = p1.x;
        x1 = p2.x;
        x2 = p3.x;
        x3 = p4.x;

        y0 = p1.y;
        y1 = p2.y;
        y2 = p3.y;
        y3 = p4.y;

        temp1 = ((x2-x0)*(y2-y3) - (x2-x3)*(y2-y0));
        temp2 = ((x1-x0)*(y2-y3) - (x2-x3)*(y1-y0));

        return (temp1/temp2);
}

Point corner(Point p1, Point p2, Point c1, Point c2)
{
        // fun linear algebra stuff
        Point br, tr, bl, tl;   // edge1, edge2, right bottom, right top, left bottom, left top

        // will make it easier to manipulate
        if(c1.x > c2.x) // c1 is right
        {
                if(c1.y > c2.y) // c1 is bottom-right (in the inverse y coordinates we use)
                {
                        br = c1;
                        tl = c2;
                        
                        bl.x = c2.x;
                        bl.y = c1.y;

                        tr.x = c1.x;
                        tr.y = c2.y;
                }
                else    // c1 is top right
                {
                        tr = c1;
                        bl = c2;

                        br.x = c1.x;
                        br.y = c2.y;

                        tl.x = c2.x;
                        tl.y = c1.y;
                }
        }

        else if (c1.x < c2.x)   // c1 is left
        {
                if(c1.y > c2.y) // c1 is bottom left
                {
                        bl = c1;
                        tr = c2;

                        tl.x = c1.x;
                        tl.y = c2.y;

                        br.x = c2.x;
                        br.y = c1.y;
                }
                else                            // c1 is top left
                {
                        tl = c1;
                        br = c2;

                        tr.x = c2.x;
                        tr.y = c1.y;

                        bl.x = c1.x;
                        bl.y = c2.y;
                }
        }

        if(p1.x > p2.x)
        {
                if(p1.y > p2.y) // either bottom left or top right
                {
                        if(p1.x == tr.x)        // is top right
                                return tr;
                        else
                                return bl;
                }
                else    // p1.y < p2.y
                {       // either top left or bottom right
                        if(p1.x == br.x)
                                return tr;
                        else
                                return bl;
                }
        }
        else    // p1.x < p2.x
        {
                if(p1.y > p2.y)
                {       // either top left or bottom right
                        if(p1.x == tl.x)
                                return tl;
                        else
                                return br;
                }
                else    // p1.y < p2.y
                {       // either top right or bottom left
                        if(p1.x == bl.x)
                                return bl;
                        else
                                return tr;
                }
        }
}